import java.util.Arrays;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        List<String> wordList = Arrays.asList(new String[]{"leet","code"});
        System.out.println(test.wordBreak("leetcode", wordList));
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        /**
         * 单词拆分
         * 状态表示：
         *  dp[i]表示以i下标元素为结尾的字符串是否能由字符串列表中的单词拼接而成
         * 状态转移方程：
         *  if(wordDict.contains(s.subString(j, i+1)) && (j == 0 || dp[j-1])) {
         *      dp[i] = True;
         *  }
         * 初始化：
         *  由状态转移方程可知，
         * 填表顺序：
         *  从左往右
         * 返回值：
         *  返回dp[n]
         *  */
        // 1 预处理
        int n = s.length();
        // 2 创建dp表
        boolean[] dp = new boolean[n];
        // 3 初始化

        // 4 填表
        for(int i = 0; i < n; i++) {
            for(int j = i; j >= 0; j--) {
                // 将已探查的部分划分为两部分进行遍历，注意边界值
                if(wordDict.contains(s.substring(j, i+1)) && (j == 0 || dp[j-1])) {
                    dp[i] = true;
                    break;
                }
            }
        }
        // 5 返回值
        return dp[n-1];
    }
}
